package LongestSubstringwithAtLeastKRepeatingCharacters;

import java.util.HashMap;

import javax.xml.bind.ValidationEvent;

public class Solution {
    public int longestSubstring(String s, int k) {
       int[][] toRight=new int[s.length()][26]; 
       int[][] toLeft=new int[s.length()][26]; 
       int ans=0;
       for (int i=s.length()-1;i>=0;i--){
    	   toRight[i][s.charAt(i)-'a']++;
    	   if (i!=s.length()-1)
    	   for (int j=0;j<26;j++)
    		   toRight[i][j]=toRight[i][j]+toRight[i+1][j];
       }
       
/*       for (int i=0;i<s.length();i--){
    	   toLeft[i][s.charAt(i)-'a']++;
    	   if (i!=0)
    	   for (int j=0;j<26;j++)
    		   toLeft[i][j]=toLeft[i][j]+toLeft[i-1][j];
       }*/
       int[] nowState=new int[26];
       boolean vaild=false;
       int index=0; int head=0;
       while (index<s.length()){
    	   char ch=s.charAt(index);
    	   if (nowState[ch-'a']+toRight[index][ch-'a']>=k) {
    		   nowState[ch-'a']++;
    		   boolean temp= check(k, nowState);
    		   if (vaild) vaild=vaild && temp;
    		   else vaild=vaild||temp;
    		   if (vaild) ans=Math.max(index-head+1,ans);
    		   index++;
    	   }
    	   else{
    		   while (index-head-1>=k){
    			   ch=s.charAt(head);
    			   nowState[ch-'a']--;
    			   boolean temp= check(k, nowState);
        		   if (vaild) vaild=vaild && temp;
        		   else vaild=vaild||temp;
        		   if (vaild) ans=Math.max(index-head-1,ans);
        		   head++;
    		   }
    		   nowState=new int[26];
    		   index++;
    		   head=index;
    	   }
    	   
       }
       return ans;
    }

	private boolean check(int k, int[] nowState) {
		for (int i=0;i<26;i++)
			   if ((nowState[i]!=0) && (nowState[i]<k)) return false; 
		return true;
	}
    
    public static void main(String args[]){
    	String s="aabcabb";
    	Solution so=new Solution();
    	System.out.println(so.longestSubstring(s, 3));
    }
}
